#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10,M = 1e5+10;
int a[N];
int ncnt,nums[N*20];
struct segment_tree2{
    int ls[N*150],rs[N*150];
    int sum[N*150],pcnt;
    void update(int &now,int l,int r,int p,int v){
        if(!now){
            now = ++pcnt;
        }
        sum[now]+=v;
        if(l == r){
            return;
        }
        int mid = (l + r)/2;
        if(p <= mid){
            update(ls[now],l,mid,p,v);
        }else{
            update(rs[now],mid+1,r,p,v);
        }
    }
    int qsum(int now,int l,int r,int x,int y){
        if(x <= l && r <= y){
            return sum[now];
        }
        int mid = (l + r)/2;
        int su = 0;
        if(x <= mid){ 
            su += qsum(ls[now],l,mid,x,y);
        }
        if(mid < y){
            su += qsum(rs[now],mid+1,r,x,y);
        }
        return su;
    }
    int binary(vector<int> nows,int l,int r,int rk){
        if(l == r){
            return l;
        }
        int mid = (l + r)/2;
        int lt = 0;
        for(int v : nows){
            lt += sum[ls[v]];
        }
        if(rk <= lt){
            for(int &v : nows){
                v = ls[v];
            }
            return binary(nows,l,mid,rk);
        }else{
            for(int &v : nows){
                v = rs[v];
            }
            return binary(nows,mid+1,r,rk - lt);
        }
    }
}sg;
struct segment_tree1{
    int rots[N<<2];
    void build(int now,int l,int r){
        for(int i = l;i <= r;i++){
            sg.update(rots[now],1,ncnt,a[i],1);
        }
        if(l == r){
            return;
        }
        int mid = (l + r)/2;
        build(now<<1,l,mid);
        build(now<<1|1,mid+1,r);
    }
    int qls(int now,int l,int r,int x,int y,int p){
        if(x <= l && r <= y){
            return sg.qsum(rots[now],1,ncnt,1,p);
        }
        int mid = (l + r)/2;
        int su = 0;
        if(x <= mid){
            su += qls(now<<1,l,mid,x,y,p);
        }
        if(mid < y){
            su += qls(now<<1|1,mid+1,r,x,y,p);
        }
        return su;
    }
    void qp(int now,int l,int r,int x,int y,vector<int> &p){
        if(x <= l && r <= y){
            p.push_back(rots[now]);
            return;
        }
        int mid = (l + r)/2;
        if(x <= mid){ 
            qp(now<<1,l,mid,x,y,p);
        }
        if(mid < y){
            qp(now<<1|1,mid+1,r,x,y,p);
        }
    }
    void update(int now,int l,int r,int p,int v){
        sg.update(rots[now],1,ncnt,a[p],-1);
        sg.update(rots[now],1,ncnt,v,1);
        if(l == r){
            a[p] = v;
            return;
        }
        int mid = (l + r)/2;
        if(p <= mid){
            update(now<<1,l,mid,p,v);
        }else{
            update(now<<1|1,mid+1,r,p,v);
        }
    }
}sg1;
int qop[N],ql[N],qr[N],qk[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        nums[++ncnt] = a[i];
    }
    for(int i = 1;i<=m;i++){
        cin>>qop[i];
        if(qop[i] == 3){
            cin>>ql[i]>>qr[i];
            nums[++ncnt] = qr[i];
        }else{
            cin>>ql[i]>>qr[i]>>qk[i];
            if(qop[i] != 2){
                nums[++ncnt] = qk[i];
            }
        }
    }
    sort(nums + 1,nums + 1 + ncnt);
    ncnt = unique(nums + 1,nums + 1 + ncnt) - nums - 1;
    for(int i = 1;i<=n;i++){
        a[i] = lower_bound(nums + 1,nums + 1 + ncnt,a[i]) - nums;
    }
    for(int i = 1;i<=m;i++){
        if(qop[i] == 3){
            qr[i] = lower_bound(nums + 1,nums + 1 + ncnt,qr[i]) - nums;
        }else if(qop[i] != 2){
            qk[i] = lower_bound(nums + 1,nums + 1 + ncnt,qk[i]) - nums;    
        }
    }
    sg1.build(1,1,n);
    for(int i = 1;i<=m;i++){
        int op = qop[i];
        if(op == 1){
            int l = ql[i],r = qr[i],k = qk[i];
            int lc = sg1.qls(1,1,n,l,r,k - 1);
            cout<<lc + 1<<'\n';
        }else if(op == 2){
            int l = ql[i],r = qr[i],k = qk[i];
            vector<int> ps;
            sg1.qp(1,1,n,l,r,ps);
            cout<<nums[sg.binary(ps,1,ncnt,k)]<<'\n';
        }else if(op == 3){
            int p = ql[i],v = qr[i];
            sg1.update(1,1,n,p,v);
        }else if(op == 4){
            int l = ql[i],r = qr[i],k = qk[i];
            int lc = sg1.qls(1,1,n,l,r,k - 1);
            if(lc == 0){
                cout<<-2147483647<<"\n";
            }else{
                vector<int> ps;
                sg1.qp(1,1,n,l,r,ps);
                cout<<nums[sg.binary(ps,1,ncnt,lc)]<<'\n';
            }
        }else{
            int l = ql[i],r = qr[i],k = qk[i];
            int lc = sg1.qls(1,1,n,l,r,k);
            if(lc == r - l + 1){
                cout<<2147483647<<'\n';
            }else{
                vector<int> ps;
                sg1.qp(1,1,n,l,r,ps);
                cout<<nums[sg.binary(ps,1,ncnt,lc + 1)]<<'\n';
            }
        }
        //cerr<<op<<'\n';
    }
}